#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
    int val;
    int exp;
    struct _node *next;
} node;

node *pa, *pb;

init()
{
    node *tmp;

    pa = malloc(sizeof(node));
    pa->val = 12;
    pa->exp = 3;
    
    tmp = malloc(sizeof(node));
    tmp->val = 2;
    tmp->exp = 5;
    pa->next = tmp;

    tmp = malloc(sizeof(node));
    tmp->val = 22;
    tmp->exp = 6;
    tmp->next = NULL;

    pa->next->next = tmp;

    pb = malloc(sizeof(node));
    pb->val = 42;
    pb->exp = 2;
    
    tmp = malloc(sizeof(node));
    tmp->val = -3;
    tmp->exp = 5;
    pb->next = tmp;

    tmp = malloc(sizeof(node));
    tmp->val = 32;
    tmp->exp = 7;
    tmp->next = NULL;

    pb->next->next = tmp;
}

void print(node *p)
{
    node *tmp;

    for (tmp = p; tmp; tmp = tmp->next)
    {
        printf("%d * x ^ %d + ", tmp->val, tmp->exp);
    }
    printf("\n");
}

node *mul(node *a, node *b)
{
    node *ta, *tb, *r, *tr, *tmp;
    r = NULL;
    for (ta = a; ta; ta = ta->next)
    {
        for (tb = b; tb; tb = tb->next)
        {
            tmp = malloc(sizeof(node));
            tmp->val = ta->val * tb->val;
            tmp->exp = ta->exp + tb->exp;
            
            if (r == NULL)
            {
                r = tmp;
                tmp->next = NULL;
                continue;
            }
            
            tr = r;
            while ((tr->next != NULL) && (tr->next->exp < tmp->exp))
                tr = tr->next;

            if (tr->next == NULL || tr->next->exp > tmp->exp)
            {
                tmp->next = tr->next;
                tr->next = tmp;
            }
            else if (tmp->val + tr->next->val == 0)
                tr->next = tr->next->next;
            else
                tr->next->val = tr->next->val + tmp->val;
        }
    
    }

    return r;
}

int main(int argc, char const* argv[])
{
    init();
    print(pa);
    print(pb);
    print(mul(pa, pb));

    return 0;
}
